package leetcode_61_80;

public class minDistance_72 {
    /**
     * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
     *
     * 你可以对一个单词进行如下三种操作：
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        /**
         *  操作不难，但是如何找到最少实在想不出来
         *  只好看官解，原来还是动态规划
         *  无需拘泥于对字符串的实际操作
         */
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];  //dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
        // 初始化第一行，即word1 为空变成 word2 最少步数，就是插入操作
        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 初始化第一列，即word2 为空，需要的最少步数，就是删除操作
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                /**
                 * 核心算法
                 * 当word1[i]!=word2[j]时
                 *
                 *                  dp[i][j] = dp[ i-1 ][ j-1 ] 表示替换操作
                 *                  word1的前i-1个字符已经变换到word2的前j-1个字符的次数，说明word1的前i-1个和word2的前j-1个字符已经完成操作；
                 *                  那么对于word1的第 i 个怎么变成word2的第 j 个呢？这两个字符都存在，那么只能是替换了；所以dp[i][j] = dp[i-1][j-1]+1;
                 *
                 *                  dp[i][j] = dp[ i-1 ][ j ]     表示删除操作
                 *                  word1的前i-1个字符已经变换到word2的前 j 个字符的次数，当前word1仅用了前 i-1 个字符就完成了到word2的前 j 个字符的操作，
                 *                  所以word1的第i个字符其实没啥用了，那么删除操作就好了；所以dp[i][j] = dp[i-1][j]+1;
                 *
                 *                  dp[i][j] = dp[ i ][ j-1 ]     表示插入操作
                 *                  word1的前i个字符已经变换到word2的前j-1个字符的次数，当前word1的第i个字符已经用了，比word2还差一个字符（因为当前只是处理了word2的前j-1个字符），
                 *                  那么word1插入一个字符来对应word2的第 j 个字符就好了；所以dp[i][j] = dp[i][j-1]+1;
                 */
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;//找到这三种操作哪个操作次数最少+1
            }
        }
        return dp[n1][n2];
    }
}
